package main

func permute(nums []int) (ans [][]int) {

	path := []int{}
	used := []bool{false, false, false}
	var dfs func(int)
	dfs = func(curr int) {
		//边界条件
		if len(path) == len(nums) {
			temp := make([]int, len(nums))
			copy(temp, path)
			ans = append(ans, temp)
			return
		}
		if curr == len(nums) {
			return
		}
		for i := 0; i < len(nums); i++ {
			//已被使用
			if used[i] {
				continue
			}
			//未被使用,加入路径
			path = append(path, nums[i])
			used[i] = true
			//进入下一层
			dfs(curr + 1)
			//回溯，撤回数组,撤回使用标记
			path = path[:len(path)-1]
			used[i] = false
		}
	}
	dfs(0)
	return
}

func main() {
	nums := []int{1, 2, 3}
	ans := permute(nums)
	for i := 0; i < len(ans); i++ {
		for j := 0; j < len(ans[0]); j++ {
			print(ans[i][j])
		}
		println()
	}
}
